Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: Letter Combinations of a Phone Number

Problem Statement

Given a string digits containing digits from 2-9, return an array of strings containing all possible letter combinations that the number could represent. You may return the answer in any order.

The mapping of digits to letters (just like on the telephone buttons) is as given below.

  • 1 -> It doesn't map any number.
  • 2 -> "abc"
  • 3 -> "def"
  • 4 -> "ghi"
  • 5 -> "jkl"
  • 6 -> "mno"
  • 7 -> "pqrs"
  • 8 -> "tuv"
  • 9 -> "wxyz"

Examples

  • Example 1:

    • Input: digits = "47"
    • Expected Output: ["gp", "gq", "gr", "gs", "hp", "hq", "hr", "hs", "ip", "iq", "ir", "is"]
    • Justification: The digit '4' maps to "ghi", and '7' maps to "pqrs". Combining these letters in every possible way gives us the expected output.
  • Example 2:

    • Input: digits = "29"
    • Expected Output: ["aw", "ax", "ay", "az", "bw", "bx", "by", "bz", "cw", "cx", "cy", "cz"]
    • Justification: The digit '2' maps to "abc", and '9' maps to "wxyz". The combinations of these letters result in the expected output.
  • Example 3:

    • Input: digits = "7"
    • Expected Output: ["p", "q", "r", "s"]
    • Justification: The digit '7' maps to "pqrs". All possible combinations of these letters are reflected in the expected output.

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

Solution

To solve this problem, we'll employ a recursive backtracking approach that efficiently explores all possible combinations of letters. This method works by starting with an empty string and adding letters corresponding to the first digit, then recursively doing the same for the next digits until all digits have been processed.

This strategy is effective because it systematically covers all combinations without repeating, ensuring we explore the entire solution space. It's akin to a depth-first search in a tree where each node represents a letter and each path from the root to a leaf forms a valid combination. By using recursion, we can simplify the code structure and directly reflect the logical flow of the solution, making the approach both intuitive and efficient for this type of combinatorial problem.

Step-by-Step Algorithm

  1. Initialize a Mapping: Create a map that associates each digit with its corresponding letters, similar to a telephone keypad.

  2. Check for Empty Input: If the input digit string is empty, return an empty list as there are no combinations possible.

  3. Start Recursion: Call a recursive helper function (backtrack) with four parameters: an empty string to build combinations, the input digit string, the current index set to 0, and an initially empty list to store the final combinations.

  4. Recursive Function - backtrack:

    • Base Case: If the current index equals the length of the digit string, it means we've constructed a full-length combination. Add the current combination string to the result list and return to explore other possibilities.
    • Iterate Through Letters: For the current digit, retrieve the corresponding letters from the map. Iterate through each letter:
      • Add the letter to the current combination string.
      • Recursively call backtrack with the updated combination string, the same digit string, the next index (current index + 1), and the result list.
      • After the recursive call returns, remove the last letter from the combination string (backtracking) to explore other letter choices for the current digit.
  5. Return Result: After exploring all combinations, return the result list containing all possible letter combinations.

Algorithm Walkthrough

Let's consider the Input: digits = "47"

  1. Initial Setup: The problem starts with an input string "47" and a mapping of digits to letters as per a telephone keypad. The goal is to find all possible letter combinations that the number could represent.

  2. Check for Empty Input: Since "47" is not an empty string, we proceed with the algorithm.

  3. Invoke Recursive Function: The backtrack function is called with the initial combination as an empty string, the input digits "47", the starting index of 0, and an empty list to store the results.

  4. Recursive Function Execution - backtrack:

    • At index 0 (first digit is '4'):
      • The map returns "ghi" for '4'.
      • For each letter in "ghi" (starting with 'g'):
        • Add 'g' to the current combination and proceed to the next digit by increasing the index.
        • Now at index 1 (second digit is '7'):
          • The map returns "pqrs" for '7'.
          • For each letter in "pqrs" (starting with 'p'):
            • Add 'p' to the current combination ("g" from the previous step). The combination now is "gp".
            • Since all digits are processed (index would move to 2, which is equal to the length of the input "47"), add "gp" to the result list.
            • Backtrack: Remove 'p' from the current combination to explore the next letter in "pqrs".
          • Repeat the process for 'q', 'r', and 's', resulting in "gq", "gr", "gs" being added to the results list after each complete iteration.
        • Backtrack to 'g': After exploring all combinations starting with 'g', remove 'g' from the current combination to backtrack and explore combinations starting with the next letter in "ghi".
      • Repeat the entire process for 'h' as the starting letter:
        • For 'h' + "pqrs", the combinations "hp", "hq", "hr", "hs" are generated and added to the results list.
      • Finally, repeat the process for 'i':
        • For 'i' + "pqrs", generate and add "ip", "iq", "ir", "is" to the results list.
    • The recursive function continues this pattern until all combinations have been explored and added to the results list.
  5. Completion: Once the recursive function has explored all combinations, the algorithm ends. The results list now contains all possible combinations: ["gp", "gq", "gr", "gs", "hp", "hq", "hr", "hs", "ip", "iq", "ir", "is"].

  6. Return Results: The list of combinations is returned as the output of the algorithm.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity:

  • Where (N) is the length of the input digit string. In the worst case, each digit corresponds to 4 letters (e.g., digits 7 or 9), leading to combinations.
  • For each combination, we spend time to construct the combination string and add it to the result list.

Space Complexity:

  • The space complexity is mainly due to the recursion call stack depth, which goes as deep as the length of the digit string (N), plus the space to hold the current combination.
  • The output list itself does not count towards the space complexity for analysis purposes, as it is part of the required output. However, if considering the output space, it would be to hold all combinations.
Letter Combinations of a Phone Number (medium)
01 Matrix (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity:

Space Complexity: